Various mechanisms exist for interacting with relational database systems. Applications often interact with relational database systems through parameterized queries, where the same SQL statement is executed repeatedly with different parameter instantiations. One approach for processing parameterized queries is to optimize each query instance, thereby generating the best plan for that instance (referred to as Optimize-Always). However, the drawback of this approach is that it can incur significant optimizer overheads, particularly for frequently executing or relatively inexpensive queries. Another simple approach, that is commonly used in today's commercial database systems, is to optimize the query for only one instance (e.g. the first query instance or an application specified instance), and reuse the resulting plan for all other instances (referred to as Optimize-Once). While the latter approach greatly reduces optimization over-heads, the chosen plan may be arbitrarily sub-optimal for other query instances. Furthermore there is no way to quantify the sub-optimality resulting from Optimize-Once.
Existing parametric query optimization (PQO) techniques approach this problem by attempting to find a middle-ground between Optimize-Always and Optimize-Once. They store a small set of carefully chosen execution plans for a parameterized query rather than only one as in Optimize-Once. When a new query instance arrives they judiciously select one of these plans to use such that the cost of the selected plan is not much worse when compared to the cost of the plan if that query instance had been optimized (as in Optimize-Always). On-line techniques for PQO may make decisions progressively—as each new query instance arrives—on which stored plan to use for that instance (or to optimize the instance), and whether to update the set of plans stored. However, existing systems may fail to provide optimal results for many queries.